package com.mzy.linear_struct.面试150题;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: mizy3
 * @Date: 2024/08/18/下午7:44
 * @Description:
 */
public class LRUTest {

    public static void main(String[] args) {
        LRUCache lru = new LRUCache(2);
        lru.put(2, 1);
        lru.put(1, 1);
        // 4 2
        System.out.println(lru.get(2));

        lru.put(4, 1);
        System.out.println(lru.get(2));

    }
}

class LRUCache {
    private Map<Integer, Node> cache = new HashMap<>();
    private Node head, tail;
    private int capacity, size;

    static class Node {
        private Node prev;
        private Node next;
        private int key;
        private int value;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        // a -> b
        // a <- b
        head.next = tail;
        tail.prev = head;
    }

    private void addHead(Node node) {
        Node next = head.next;
        node.prev = head;
        node.next = next;
        next.prev = node;
        head.next = node;
    }

    private Node removeLast() {
        Node last = tail.prev;
        last.prev.next = tail;
        tail.prev = last.prev;
        return last;
    }

    private Node remove(Node node) {
        Node e = cache.get(node.key);
        Node prev = e.prev;
        Node next = e.next;
        prev.next = next;
        next.prev = prev;
        return e;
    }

    private void moveToHead(Node node) {
        remove(node);
        addHead(node);
    }

    public void put(int key, int value) {
        Node node = new Node(key, value);

        // 判断是否是更新
        if (cache.containsKey(node.key)) {
            remove(node);
            addHead(node);
            cache.put(node.key, node);
        } else {
            // 新增
            // 判断是否满了
            if (size >= capacity) {
                Node removeNode = removeLast();
                cache.remove(removeNode.key);
                addHead(node);
                cache.put(node.key, node);
            }else {
                addHead(node);
                cache.put(node.key, node);
                size++;
            }
        }

    }

    public int get(int key) {
        Node e = cache.get(key);
        if (e == null) {
            return -1;
        }
        remove(e);
        addHead(e);
        return e.value;
    }


}



